package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class S23 {
    /*
    回溯算法  dfs
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    ArrayList<Integer>arrayList = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        dfs(num, 0, new boolean[num.length]);
//        ArrayList<ArrayList<Integer>> result0 = new ArrayList<>();
//        for(ArrayList<Integer> arr:result) {
//            if(!result0.contains(arr)) {
//                result0.add(arr);
//            }
//        }
        return result;
    }
    public void dfs(int[] num, int depth, boolean[] used) {
        if (num.length == depth) {
            result.add(new ArrayList<>(arrayList));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if(i>=1 && num[i] == num[i-1] && used[i-1]) {
                continue;
            }
            if (!used[i]) {
                arrayList.add(num[i]);
                used[i] = true;
                dfs(num, depth+1, used);
                //回退
                arrayList.remove(arrayList.size()-1);
                used[i] = false;
            }

        }
    }

    public static void main(String[] args) {
        S23 s23 = new S23();
        int[] arr = {1,3};
        ArrayList<ArrayList<Integer>> arrayList = s23.permuteUnique(arr);
        System.out.println(arrayList);
    }

}
